/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        990.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/17 18:24
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给定一个由表示变量之间关系的字符串方程组成的数组，
// 每个字符串方程 equations[i] 的长度为 4，
// 并采用两种不同的形式之一："a==b" 或"a!=b"。
// 在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
//
//只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回true，否则返回 false。
#include "../header.h"

class UF {
public:
    explicit UF(int n) : parent(n), size(n, 1), count(n) {
        for (int i = 0; i < n; ++i)
            parent[i] = i;
    }

    /* 将 p 和 q 连接 */
    void Union(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        if (rootp == rootq)
            return;
        if (size[rootp] > size[rootq]) {
            parent[rootq] = rootp;
            size[rootp] += size[rootq];
        } else {
            parent[rootp] = rootq;
            size[rootq] += size[rootp];
        }
        count--;
    }

    /* 判断 p 和 q 是否连通 */
    bool Connected(int p, int q) {
        int rootp = find(p);
        int rootq = find(q);
        if (rootp == rootq)
            return true;
        return false;
    }

    /* 返回图中有多少个连通分量 */
    int Count() {
        return count;
    }

private:
    vector<int> parent;
    vector<int> size; // size[i] i的节点数
    int count;

    int find(int p) {
        while (parent[p] != p) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }
};

class Solution {
public:
    bool equationsPossible(vector<string> &equations) {
        UF uf(26);
        for (auto &eq : equations)
            if (eq[1] == '=')
                uf.Union(eq[0] - 'a', eq[3] - 'a');
        for (auto &eq : equations)
            if (eq[1] == '!' && uf.Connected(eq[0] - 'a', eq[3] - 'a'))
                return false;
        return true;
    }
};
